package com.sheng.leetcode.year2022.swordfingeroffer.day14;

import org.junit.Test;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * @author liusheng
 * @date 2022/09/13
 *<p>
 * 面试题13. 机器人的运动范围<p>
 *<p>
 * 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。<p>
 * 一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），<p>
 * 也不能进入行坐标和列坐标的数位之和大于k的格子。<p>
 * 例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。<p>
 * 但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？<p>
 *<p>
 * 示例 1：<p>
 * 输入：m = 2, n = 3, k = 1<p>
 * 输出：3<p>
 *<p>
 * 示例 2：<p>
 * 输入：m = 3, n = 1, k = 0<p>
 * 输出：1<p>
 *<p>
 * 提示：<p>
 *<p>
 * 1 <= n,m <= 100<p>
 * 0 <= k<= 20<p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword0013 {

    @Test
    public void test01() {
//        int m = 2, n = 3, k = 1;
        int m = 3, n = 1, k = 0;
        System.out.println(new Solution13().movingCount(m, n, k));
    }
}

/**
 * 超时
 */
//class Solution13 {
//    int o;
//    Map<String, Integer> map;
//    int[][] ints;
//    int x, y;
//    public int movingCount(int m, int n, int k) {
//        o = k;
//        map = new HashMap<>(16);
//        ints = new int[m][n];
//        x = m;
//        y = n;
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                ints[i][j] = 0;
//            }
//        }
//        dfs(0, 0);
//        return map.size();
//    }
//
//    public void dfs(int i, int j) {
//        if (i < 0 || i >= x || j < 0 || j >= y) {
//            return;
//        }
//        if (ints[i][j] == 1) {
//            return;
//        }
//        int sum = 0;
//        for (String s : String.valueOf(i).split("")) {
//            sum += Integer.parseInt(s);
//        }
//        for (String s : String.valueOf(j).split("")) {
//            sum += Integer.parseInt(s);
//        }
//        if (sum > o) {
//            return;
//        }
//        ints[i][j] = 1;
//        map.put(i + "*" + j, map.getOrDefault(i + "*" + j, 0) + 1);
//        dfs(i - 1, j);
//        dfs(i + 1, j);
//        dfs(i, j - 1);
//        dfs(i, j + 1);
//        ints[i][j] = 0;
//    }
//}

class Solution13 {
    public int movingCount(int m, int n, int k) {
        if (k == 0) {
            return 1;
        }
        Queue<int[]> queue = new LinkedList<int[]>();
        // 向右和向下的方向数组
        int[] dx = {0, 1};
        int[] dy = {1, 0};
        // 代表对应路径是否可以行走
        boolean[][] vis = new boolean[m][n];
        queue.offer(new int[]{0, 0});
        // 第一个位置赋值为true
        vis[0][0] = true;
        // 代表到达的格子的数量，第一个格子肯定能走，所以默认为1
        int ans = 1;
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int x = cell[0], y = cell[1];
            for (int i = 0; i < 2; ++i) {
                int tx = dx[i] + x;
                int ty = dy[i] + y;
                // 如果超出矩阵边界，或者已经走过当前位置，或者不符合要求
                if (tx < 0 || tx >= m || ty < 0 || ty >= n || vis[tx][ty] || get(tx) + get(ty) > k) {
                    continue;
                }
                // 添加元素到队尾
                queue.offer(new int[]{tx, ty});
                // 代表当前位置可以行走
                vis[tx][ty] = true;
                // 到达格子数 + 1
                ans++;
            }
        }
        return ans;
    }

    /**
     * 获取整数中每个位数相加之后的值
     *
     * @param x 要计算的整数
     * @return 每个位数相加之后的值
     */
    private int get(int x) {
        int res = 0;
        while (x != 0) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }
}
//
//作者：LeetCode-Solution
//链接：https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/solution/ji-qi-ren-de-yun-dong-fan-wei-by-leetcode-solution/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
